package mybinarytree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yi
 * Date: 2024-07-21
 * Time: 10:01
 */
public class BinaryTree {
    public int i = 0;
    static class TreeNode{
        public char val;
        public TreeNode lift;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    private TreeNode root;//根节点
    //创建一棵树
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.lift = B;
        A.right = C;
        B.lift = D;
        B.right = E;
        E.right = H;
        C.lift = F;
        C.right = G;

        return A;
    }

    //前序序列创建二叉树
    public TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.lift = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }
    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null) return;
        System.out.print(root.val+" ");
        this.preOrder(root.lift);
        this.preOrder(root.right);
    }

    /*public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if(root == null) return list;
        list.add(root);
        List<TreeNode> liftTree = this.preOrder2(root.lift);
        list.addAll(liftTree);
        List<TreeNode> rightTree = this.preOrder2(root.right);
        list.addAll(rightTree);
        return list;
    }*/
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null) return;
        this.inOrder(root.lift);
        System.out.print(root.val+" ");
        this.inOrder(root.right);
    }

    /*public List<TreeNode> inOrder2(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if(root == null) return list;
        list.addAll(this.inOrder2(root.lift));
        list.add(root);
        list.addAll(this.inOrder2(root.right));
        return list;
    }*/
    //后续遍历
    public void postOrder(TreeNode root){
        if(root == null) return;
        this.postOrder(root.lift);
        this.postOrder(root.right);
        System.out.print(root.val+" ");
    }

        /*public List<TreeNode> inOrder2(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if(root == null) return list;
        list.addAll(this.inOrder2(root.lift));
        list.addAll(this.inOrder2(root.right));
        list.add(root);
        return list;
    }*/

    //求一棵树的总结点数
     public int size(TreeNode root){
        if(root == null) return 0;
        return size(root.lift) + size(root.right) + 1;
     }
    //求一棵树的叶子节点数
    public int leafSize(TreeNode root){
        if(root == null) return 0;
        if(root.lift == null && root.right == null){
            return 1;
        }
        return leafSize(root.lift) + leafSize(root.right);
    }

    //获取第K层的节点个数
      public int getKLevelCount(TreeNode root,int K){
         if(root == null) return 0;
         if(K == 1) return 1;
         return getKLevelCount(root.lift,K-1) + getKLevelCount(root.right,K-1);
      }

      //获取树的高度
    public int getHeight(TreeNode root){
         if(root == null) return 0;
         return (getHeight(root.lift) > getHeight(root.right) ? getHeight(root.lift) : getHeight(root.right)) + 1;
    }

    //判断一棵树中是否有指定节点
    public boolean find(TreeNode root,char key){
        if(root == null) return false;
        if(root.val == key) return true;
        boolean liftFind = find(root.lift,key);
        if(liftFind == true) return true;
        boolean rightFind = find(root.right,key);
        if(rightFind == true) return true;
        return false;
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.lift != null){
                queue.offer(cur.lift);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    public List<List<TreeNode>> levelOrder2(TreeNode root){
         List<List<TreeNode>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return ret;
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<TreeNode> tmp = new ArrayList<>();
            while(size != 0){
                TreeNode cur = queue.poll();
                tmp.add(cur);
                size--;
                if(cur.lift != null){
                    queue.offer(cur.lift);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
            }
        return ret;
    }


    //判断是否是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return true;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur == null){
                for(TreeNode x : queue) {
                    if(x != null){
                        return false;
                    }
                }
            }else{
                if(cur.lift != null){
                    queue.offer(cur.lift);
                }else{
                    queue.offer(null);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }else{
                    queue.offer(null);
                }
            }
        }
        return true;
    }

    //非递归前序遍历二叉树
    public void preOrderOn(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return;
        TreeNode cur = root;
        TreeNode rop = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.lift;
            }
            rop = stack.pop();
            cur = rop.right;
        }
    }
    //非递归中序遍历二叉树
    public void inOrderOn(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return;
        TreeNode cur = root;
        TreeNode rop = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.lift;
            }
            rop = stack.pop();
            System.out.print(rop.val+" ");
            cur = rop.right;
        }
    }

    //非递归后序遍历二叉树
    public void postOrderOn(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return;
        TreeNode cur = root;
        TreeNode rop = null;
        TreeNode flag = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.lift;
            }
            rop = stack.peek();
            if(rop.right == null || rop.right == flag){
                stack.pop();
                System.out.print(rop.val+" ");
                flag = rop;
            }else{
                cur = rop.right;
            }
        }
    }
}
